МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
Кафедра ЗІ
Лабороторна робота №3
з курсу «Методи і засоби криптологічних перетворень»
на тему: «Конгруентні генератори. Регістри зсуву»
Мета роботи: ознайомитися з конгруентними генераторами псевдовипадкових послідовностей бітів, регістрами зсуву з зворотним зв’язком.
Завдання
Написати програму шифрування і розшифрування на мові програмування С/С++ для реалізації регістра зсуву з лінійним зворотним зв’язком на основі регістру Фібоначчі 8-го порядку.
Коротокі теоретичні відомості
Лінійним конгруентним генератором (ЛКГ) з параметрами (x0, a, c, N) називається програмний генератор, утворюючий псевдовипадкову послідовність x1,x2,…є А, A ={0,1,…,N-1} за допомогою рекурентного відношення:
(1.1)
Параметри цього генератора (1.1) мають наступний зміст: - початкове, або стартове, значення; - ненульовий множник; - приріст, - модуль, рівний потужності алфавіту .
Якщо приріст , то генератор (1.1) називається мультиплікативним конгруентним генератором (МКГ), а якщо , то змішаним конгруентним генератором (ЗКГ).
Лінійним регістром зсуву з зворотним зв’язком (Linear Feedback Shift Register, скорочено РЗЛЗЗ) називається логічний прилад.
РЗЛЗЗ складається з комірок пам’яті, двійкові стани яких в момент часу характеризуються значеннями . Виходи комірок пам’яті зв’язані не тільки послідовно один з одним, але й з суматорами в відповідності з коефіцієнтами передачі якщо , то значення і-ї комірки передається на один із виходів і-го суматора; якщо , то така передача відсутня. Припускаємо . Стан РЗЛЗЗ в даний момент часу задається двійковим n-вектор-стовпцем .
Загальний вид рекурентного співвідношення, що визначає генератор Фібоначчі, задається рівнянням
Рис.1.2. Регістр зсуву з лінійним зворотнім зв’язком
, (1.9)
де - параметри генератора; елемент представляє собою двійковий k-вектор і дія виконується покомпонентно.
РЗЛЗЗ в програмній реалізації працюють досить повільно, і швидкість можна збільшити застосуванням для програмування мови Асемблер замість Сі. Ще одне можливе рішення - запускати 16 РЗЛЗЗ (або 32, залежно від розміру слова в комп'ютері) у паралельному режимі. Така схема використовує масив слів, так що кожна бітова комірка регістру представлена окремим РЗЛЗЗ. При умові, що всі вони мають один і той же поліном зворотного зв'язку, така схема працює досить швидко. У загальному випадку найкращий спосіб оновлювати стани регістрів зсуву - це множити поточний стан на відповідні двійкові матриці.
У даному прикладі розглянемо поліном вигляду:
Схема матиме такий вигляд:
Текст програми шифрування
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#include <math.h>
const size_t small_buff = 20;
const size_t big_buff = 102400;
void main()
{
clrscr();
char text[small_buff];
char bigtext[big_buff];
FILE *infile = fopen( "f:\\ot.txt", "r" );
size_t read_len = 0;
size_t file_len = 0;
while( read_len = fread(text, 1, small_buff, infile ) )
{
memcpy( bigtext + file_len, text, read_len );
file_len += read_len;
}
int j,n,j1,i,n1,pzr;int k[10000];int kl[10000]; j1=0;int b[10000];
for(n=0;n<file_len*8;n++)
{kl[n]=0; k[n]=0;b[n]=0;}
/*zadaemo pochatkove znachennya registru*/
printf("vvedit chyslo=");
scanf("%d",&pzr);
for(n=7;n>=0;n--)
{ if (pzr -pow(2,n)<0)
b[n]=0;
else {b[n]=1;pzr = pzr-pow(2,n);}
}
/*generuemo poslidovnist psevdovypadkovyh bitiv*/
for(i=0;i<(file_len*8);i++)
{ b[i+8]=(((b[i+5])^b[i+4])^b[i+2]);
}
/*generuemo kluch*/
for(n=0;n<file_len;n++)
{
for(j=0;j<=7;j++,j1++)
{ {if (1==b[j1])
k[j]=pow(2,j);
else continue;}
kl[n]=kl[n]+k[j];
}
}
/*zdiusnuemo operaciu xor*/
for(n1=0;n1<file_len;n1++)
{ bigtext[n1]=bigtext[n1]^kl[n1];}
FILE *outfile = fopen( "f:\\ct.txt", "w" );
fwrite( bigtext, 1, file_len, outfile );
fclose( infi...
